package 刷题.leedcode102;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 空树：直接返回null
 * 构造队列用来作为辅助
 * 先将根节点放入队列中，不断遍历队列
 * 拿出根节点，判断有没有左右子树，有就放入队列中，此时队列中的严肃仅剩左右孩子
 * 迭代实现，持续这个过程
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root){
        //将每层结点保存在一个list中
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        //创建一个队列
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        //循环条件：队列不为空
        while(!q.isEmpty()) {
            //遍历当前层的所有结点
            //得到队列中元素个数
            int size = q.size();
            //保存本层中的所有节点，大小为size正好
            List<Integer> level = new ArrayList<>(size);
            for(int i = 0;i < size ; i++){
                //保存值
                TreeNode cur = q.poll();
                level.add(cur.val);
                //判断有没左右节点并进行入队列操作
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            //将本层节点保存到数组中
            ret.add(level);
        }
        return ret;
    }
}
